#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<stdlib.h>

struct listnode
{
	int val;
	struct listnode* next;
};

struct listnode* mergelist(struct listnode* L1, struct listnode* L2)
{
	struct listnode dummy;
	struct listnode* cur = &dummy;
	dummy.next = NULL;

	while (L1 != NULL && L2 != NULL)
	{
		if (L1->val < L2->val)
		{
			if (cur->next == NULL || cur->val != L1->val)
			{
				cur->next = L1;
				cur = L1;
			}
			L1 = L1->next;
		}
		else if (L2->val < L1->val)
		{
			if (cur->next == NULL || cur->val != L2->val)
			{
				cur->next = L2;
				cur = L2;
			}
			L2 = L2->next;
		}
		else
		{
			if (cur->next == NULL || cur->val != L1->val)
			{
				cur->next = L1;
				cur = L1;
			}
			L1 = L1->next;
			L2 = L2->next;
		}
	}

	while (L1 != NULL)
	{
		if (cur->next == NULL || cur->val != L1->val)
		{
			cur->next = L1;
			cur = L1;
		}
		L1 = L1->next;
	}

	while (L2 != NULL)
	{
		if (cur->next == NULL || cur->val != L2->val)
		{
			cur->next = L2;
			cur = L2;
		}
		L2 = L2->next;
	}

	return dummy.next;
}

void printlistnode(struct listnode* head)
{
	while (head)
	{
		printf("%d ", head->val);
		head = head->next;
	}
}

struct listnode* creatnode(int n)
{
	struct listnode* newnode = (struct listnode*)malloc(sizeof(struct listnode));
	newnode->val = n;
	newnode->next = NULL;
	return newnode;
}

int main()
{
	struct listnode* L1 = creatnode(1);
	L1->next = creatnode(3);
	L1->next->next = creatnode(5);

	struct listnode* L2 = creatnode(2);
	L2->next = creatnode(4);
	L2->next->next = creatnode(8);

	struct listnode* mergedlist = mergelist(L1, L2);

	printlistnode(mergedlist);
	
	return 0;
}